public class CountingBits {
    public int[] countBits1(int n) {
        int[] ret = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            ret[i] = countBit(i);
        }
        return ret;
    }

    public int countBit(int n) {
        int ret = 0;
        while(n != 0) {
            ret++;
            n &= (n-1);
        }
        return ret;
    }

    // dp[i]表示: i 元素二进制表示中 1 的个数
    public int[] countBits2(int n) {
        int[] dp = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            if(i % 2 == 0) {
                // 如果是偶数(1 的个数等于 i / 2 的二进制 1 的个数)
                dp[i] = dp[i / 2];
            }else {
                // 如果是奇数(就等于前一个元素的二进制 1 的个数 + 1)
                dp[i] = dp[i-1] + 1;
            }
        }
        return dp;
    }

    public int[] countBits3(int n) {
        int[] dp = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            if((i & 1) == 0) {
                // 只有最低位是1的数, &1 才得1, 也就是说只有是奇数 &1 才能得1,得 0 的是偶数
                dp[i] = dp[i >> 1];
            }else {
                // 如果是奇数(就等于前一个元素的二进制 1 的个数 + 1)
                dp[i] = dp[i-1] + 1;
            }
        }
        return dp;
    }

    public int[] countBits(int n) {
        int[] dp = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            // i & 1 奇数运算结果为1, 偶数运算结果为 0
            dp[i] = dp[i >> 1] + (i & 1);
        }
        return dp;
    }
}
